//
//  23. 合并K个升序链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/23.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution23 {
    // 合并K个有序链表
    // 1. 合并两个有序链表 o(n)
    // 2. 两两向合并可以做到logn
    func mergeKLists2(_ lists: [ListNode?]) -> ListNode? {
        return recursive(lists, 0,lists.count - 1)
    }
    func recursive(_ lists: [ListNode?], _ start: Int, _ end: Int) -> ListNode? {
        if start == end {
            return lists[start]
        }
        guard start < end else {
            return nil
        }
        let mid = (start + end) / 2
        let node1 = recursive(lists, start, mid)
        let node2 = recursive(lists, mid + 1, end)
        return mergeTowList(node1, node2)
    }
    func mergeTowList(_ node1: ListNode?, _ node2: ListNode?) -> ListNode? {
        let newHead = ListNode(-1)
        var p: ListNode? = newHead
        var p1: ListNode? = node1
        var p2: ListNode? = node2
        while p1 != nil , p2 != nil{
            if p1!.val <= p2!.val {
                p?.next = p1
                p1 = p1?.next
            } else {
                p?.next = p2
                p2 = p2?.next
            }
            p = p?.next
        }
        if p1 != nil {
            p?.next = p1
        }
        if p2 != nil {
            p?.next = p2
        }
        return newHead.next
    }
    
    static func test() {
        let link1 = [1,4,5]
        let link2 = [1,3,4]
        let link3 = [2,6]
        
        let root1 = createNode(link1)
        let root2 = createNode(link2)
        let root3 = createNode(link3)
        let lists = [root1,root2,root3]
        
        let solution = Solution23()
        let result = solution.mergeKLists2(lists)
        print(result)
    }
    static func createNode(_ link: [Int]) -> ListNode?{
        var root: ListNode?
        var p: ListNode?
        for item in link {
            if root == nil {
                root = ListNode(item)
                p = root
            } else {
                p?.next = ListNode(item)
                p = p?.next
            }
        }
        return root
    }
}
